package java;

import java.util.Arrays;

public class Question34 {
    public static void main(String[] args) {
        int[] ints = {5,7,7,8,8,10};
        System.out.println(Arrays.toString(searchRange(ints,5)));
    }
    public static int[] searchRange(int[] nums, int target) {
        int[] res = {-1,-1};
        if (nums == null || nums.length < 1) {
            return res;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left <= right){
            int center = (left + right)/2;
            if (target < nums[center]){
                right = center - 1;
            }else if (target > nums[center]){
                left = center + 1;
            }else {
                res[0] = findBord(nums,left,center,target,0);
                res[1] = findBord(nums,center,right,target,1);
                return res;
            }
        }
        return res;
    }

    private static int findBord(int[] nums, int left, int right, int target, int flag) {
        while (left <= right){
            int center = (left + right)/2;
            if (nums[center] == target){
                if (flag == 0){
                    if (center - 1 == -1 ||nums[center - 1] != target){
                        return center;
                    }else {
                        right = center - 1;
                    }
                }else {
                    if (center + 1 == nums.length || nums[center + 1] != target){
                        return center;
                    }else {
                        left = center + 1;
                    }
                }
            }else {
                if (target < nums[center]){
                    right = center - 1;
                }else {
                    left = center + 1;
                }
            }
        }

        return -1;
    }
}
